#include <bits/stdc++.h>

using namespace std;

class Solution {
 public:
  vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
    vector<bool> ans(queries.size(), true);

    vector<int> specialQJ(nums.size(), nums.size() - 1);

    int start = nums.size() - 2, end = nums.size() - 1;
    while (start >= 0) {
      if (((nums[start] + nums[start + 1]) & 1) == 0) {
        end = start;
      }
      specialQJ[start] = end;
      start--;
    }

    for (int i = 0; i < queries.size(); i++) {
      if (queries[i][1] > specialQJ[queries[i][0]]) {
        ans[i] = false;
      }
    }

    return ans;
  }
};

int main(int argc, const char** argv) {
  Solution solution = Solution();
  vector<int> nums = {3, 4, 1, 2, 6};
  vector<vector<int>> querys = {{0, 4}};
  vector<bool> res = solution.isArraySpecial(nums, querys);
  for (auto i : res) {
    std::cout << to_string(i) << std::endl;
  }
  return 0;
}